package com.njupt.LinkTable;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/18 10:57
 * @Description: 21. 合并两个有序链表
 * @Version: 1.0
 */


public class MergeTwoLists_21 {

    /**
     * 采用额外的空间
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode curA = list1;
        ListNode curB = list2;
        ListNode head = new ListNode(-1);
        ListNode p = head;

        while(curA != null && curB != null){
            if(curA.val <= curB.val){
                ListNode node = new ListNode(curA.val);
                p.next = node;
                p = node;
                curA = curA.next;
            }else {
                ListNode node = new ListNode(curB.val);
                p.next = node;
                p = node;
                curB = curB.next;
            }
        }
        while(curA != null){
            ListNode node = new ListNode(curA.val);
            p.next = node;
            p = node;
            curA = curA.next;
        }
        while(curB != null){
            ListNode node = new ListNode(curB.val);
            p.next = node;
            p = node;
            curB =curB.next;
        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(4);
        
        ListNode head2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        head1.next = node1; node1.next = node2;
        
        head2.next = node3; node3.next = node4;

        MergeTwoLists_21 test = new MergeTwoLists_21();
        ListNode listNode = test.mergeTwoLists(head1, head2);

        ListNode p = listNode;
        while(p != null){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
}
